package medium

import "math"

/*
时间复杂度：O(N)
空间复杂度：O(N)

*/

var MOD = int(math.Pow(10, 9)) + 7

func sumSubarrayMins(arr []int) int {
	arr = append(arr, 0)
	stack := make([]int, 0)
	ans := 0
	for i, v := range arr {
		// stack中是非严格单调递增的
		// 例如: 1 1 1  计算第一个1的时候有子数组[1] [1 1] [1 1 1]
		// 而计算第二个1的子数组时，只需要计算[1]即可, 也就是对于元素arr[i], 找到其左边第一个<=arr[i]的位置left
		// 找到右边第一个<arr[i]的位置right, 然后左边包括arr[i]自己有 i-left个元素（注意：不统计左边=arr[i]的数）
		// 右边包括arr[i]自己有right-i个元素(注意：右边是会统计=arr[i]的元素的)
		// 这里有一个小技巧，即总共可以构成的子数组为: (i-left)*(right-i)=1+left+right+(i-left-1)*(right-i-1)
		// 例如arr[i],不包括自己，假设左边有2个，右边有3个，
		// 总共有: 1+2+3+2*3=12个(1是arr[i]自己，2是arr[i]与左边构成的子数组，3是arr[i]与右边构成的子数组)
		// 其实就等于包括自己，左边有3个，右边有4个，总共3*4=12个
		for len(stack) > 0 && v < arr[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			preIdx := -1
			if len(stack) > 0 {
				preIdx = stack[len(stack)-1]
			}
			ans += (idx - preIdx) * (i - idx) * arr[idx] % MOD
			ans %= MOD
		}
		stack = append(stack, i)
	}
	return ans
}
